|
In graph theory, a clique graph of an undirected graph ''G'' is another graph ''K''(''G'') that represents the structure of cliques in ''G''. Clique graphs were discussed at least as early as 1968, and a characterization of clique graphs was given in 1971. ==Formal definition== A clique of a graph ''G'' is a set ''X'' of vertices of ''G'' with the property that every pair of distinct vertices in ''X'' are adjacent in ''G''. A maximal clique of a graph ''G'' is a clique ''X'' of vertices of ''G'', such that there is no clique ''Y'' of vertices of ''G'' that contains all of ''X'' and at least one other vertex. Given a graph ''G'', its clique graph ''K''(''G'') is a graph such that * every vertex of ''K''(''G'') represents a maximal clique of ''G''; and * two vertices of ''K''(''G'') are adjacent when the underlying cliques in ''G'' share at least one vertex in common. The clique graph ''K''(''G'') can also be characterized as the intersection graph of the maximal cliques of ''G''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Clique graph」の詳細全文を読む スポンサード リンク
|